import javax.sound.midi.Soundbank;
import java.util.Arrays;
import java.util.Scanner;

public class MergeSort {
    /**
     * 进行归并排序：
     * 归并排序的思想是对数组不断二分，比较两个数组的第一个元素进行比较，指针后移
     * 重复这个过程即可
     */
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        System.out.print("输入数组的大小：");
        int n=in.nextInt();
        System.out.println("依次输入数组的元素值：");
        int[] a=new int[n];
        for(int i=0;i<n;i++){
            a[i]=in.nextInt();
        }
        System.out.println("原始数组为："+ Arrays.toString(a));

        merge(a);
        System.out.println("排序后的数组为："+Arrays.toString(a));
    }

    public static void merge(int[] arr){
        if(arr==null || arr.length<2){
            return;
        }
       sortProcess(arr, 0, arr.length-1);
    }

    public static void sortProcess(int[] arr,int L,int R){
        if(L==R){
            // 终止条件
            return;
        }
        int mid=L+(R-L)/2;
        sortProcess(arr,L,mid);
        sortProcess(arr,mid+1,R);
        m(arr,L,mid,R);
    }
    public static void m(int[] arr,int L,int mid,int R){
        int[] help=new int[R-L+1];
        int i=0;
        int p1=L;
        int p2=mid+1;
        while(p1<=mid && p2<=R){
            help[i++]=arr[p1]<arr[p2]?arr[p1++]:arr[p2++];
        }
        while(p1<=mid){
            help[i++]=arr[p1++];
        }
        while (p2<=R){
            help[i++]=arr[p2++];
        }
        for(i=0;i<help.length;i++){
            arr[L+i]=help[i];
        }
    }
}
